package leetcode.linkedlist;

public class ReverseLinkedList206 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution1 {
        public ListNode reverseList(ListNode head) {
            ListNode newHead = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = newHead;
                newHead = head;
                head = next;
            }
            return newHead;
        }
    }

    class Solution2 {
        public ListNode reverseList(ListNode head) {
            return reverseList(head, null);
        }

        ListNode reverseList(ListNode head, ListNode prev) {
           if (head == null) {
               return prev;
           }
           ListNode next = head.next;
           head.next = prev;
           return reverseList(next, head);
        }
    }
}
